package Testdemo5;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-07-09
 * Time：14:14
 */
public class Test2 {
}


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */




class Solution {

    // 制造一个全局变量用来保存
    List<String> list = new ArrayList<>();


    /**
     *
     *
     *
     *  全局变量会保存， 局部变量会更新的原则
     *  在深搜中
     *  局部变量一般作为参数列表
     *  全局遍历一般作为 返回值来进行使用
     * @param root
     * @return
     */


    public List<String> binaryTreePaths(TreeNode root) {

        // 局部遍历作为函数参数列表
        // 在局部变量中每次都会更新
        // 注意全局变量和局部变量的区别
        String path = "";
        pfs(root , path);
        return list;
    }


    /**
     * 深搜题目
     * 二叉树的所有路径
     * @param root
     * @param path
     */

    public void  pfs(TreeNode root, String path) {
        // 判断自身节点是否为 null
        if(root==null) return;

        // 判断是否是叶子节点
        if( root.left==null && root.right==null) {
            path += root.val;
            list.add(path);
            return ;
        }


        // 添加节点
        path +=  root.val;
        path += "->";
        // 前序遍历
        pfs(root.left , path);
        pfs(root.right , path);

    }


    /**
     * 注意全局变量的区别
     * StringBuilder 用来连接
     * @param root 根
     * @return 返回顺序表
     */
    public List<String> binaryTreePaths2(TreeNode root) {

        // 局部遍历作为函数参数列表
        StringBuilder  path = new StringBuilder();
        pfs(root , path);
        return list;
    }

    public void  pfs(TreeNode root,StringBuilder  _path) {
        // 由原来的全局改成局部
        // 注意这里每次都需要更新局部变量
        StringBuilder  path = new StringBuilder(_path);
        // 判断自身节点是否为 null
        if(root==null) return;

        // 判断是否是叶子节点
        if( root.left==null && root.right==null) {
            path.append(Integer.toString( root.val));
            list.add(path.toString());
            return ;
        }

        // 添加节点
        path.append(Integer.toString(root.val));
        path.append("->");
        // 前序遍历
        pfs(root.left , path);
        pfs(root.right , path);

    }





    // 定义一个全局变量
    long prev = Long.MIN_VALUE;


    /**
     * 返回一个布尔值
     *
     * 题目：验证二叉搜索树
     * 利用中序遍历的有序性
     * 添加一个前序变量的节点
     * @param root 根节点
     * @return
     */
    public boolean isValidBST(TreeNode root) {

        return bfs(root);
    }

    boolean  bfs(TreeNode root ) {
        // 返回为 null 的情况
        if(root==null) {
            return true;
        }



        // 判断左边是否是符合搜索树
        boolean left = bfs(root.left);
        // 左子树判断
        if(!left) {
            return false;
        }

        // 记录前面的大小
        if((long)root.val > prev) {
            prev = root.val;

        } else {
            return false;
        }

        // 判断右边是否符合搜索树
        boolean right = bfs(root.right);

        // 右子树判断
        if(!right) {
            return false;
        }



        return true;




    }



        int  desc = -1;
        int m;


    /**
     * 寻找二叉搜索树中第K 个最小的元素
     * 本质上
     * 先利用中序遍历
     * 然后利用全局变量不变原则
     * 把需要的第K 最小的值保存下来即可
     * @param root 根节点
     * @param k 第 K 个
     * @return 返回第 K 个较小的
     */
    public int kthSmallest(TreeNode root, int k) {
            m=k;
            bfs1(root);
            return desc;
        }


        void  bfs1(TreeNode root) {
            // 判断是否为 null
            if(root==null) {
                return ;
            }

            // 进行中序遍历
            bfs(root.left);



            m--;
            // 判断左子树
            if(m == 0) {
                desc = root.val;
                return ;
            }


            bfs(root.right);


            List<List<Integer>> lists = new ArrayList<>();
        }


//    public static void main(String[] args) {
//         int[] array= {1,2,3,4,5};
//         permute(array);
//        System.out.println(ret);
//    }



    static List<List<Integer>> ret ;
   static List path ;
   static boolean[]  check ;

    /**
     *
     *  题目： 全排列
     *  全排列的精髓在于
     *  1. 实现 三个全局变量
     *  2. 一个全局变量作为 返回值
     *  3. 一个全局变量用来记录每种情况的值
     *  4. 一个全局变量用来记录是否出现过该值
     *
     *  利用全局变量来记录所有值
     *  在每一个 num.length 时
     *  都需要遍历一遍
     *  注意每一个都要遍历一遍
     *
     *  最终把标识和数组中的最后一个元素去掉
     * @param nums 一维数组
     * @return 其中一个二维顺序表的返回值
     */
    public static List<List<Integer>> permute(int[] nums) {

        ret = new ArrayList<>();

        // 假设一个路径
        path = new ArrayList<>();


        // 用来记录下标是否用过
        // 进行剪枝操作
        check= new boolean[nums.length];

        // 深搜
        dfs(nums);
        return ret;
    }

   static void   dfs(int [] nums) {
        // 终止条件
        if(path.size() == nums.length) {
            // 注意这里一定继续 new 一个二维数组
            // path 作为二维数组中的基本元素
            ret.add(new ArrayList<>(path));
            return;
        }


        // 进行输入
       for (int i = 0; i < nums.length; i++) {
           // 检查是否存在
           if(!check[i]) {


               path.add(nums[i]);
               check[i]=true;
               // 进行深搜
               dfs(nums);

               // 注意进入的每个数组都要重新放置为 false
               // 回溯时置为false
               check[i]= false;

               // 注意这里得到把尾部的大小给删去
               // 实现回溯的效果
               path.remove(path.size()-1);
           }
       }

    }


    // 返回值
    List<List<Integer>> ret1;
    // 记录路径
    List<Integer> path1 ;
    public List<List<Integer>> subsets(int[] nums) {
        // 返回值
        ret1 = new ArrayList<>();

        // 路径
        path1 = new ArrayList<>();

        // 开始深搜
        dfs(nums,0);

        return ret1;

    }

    /**
     *  得到一个集合的子集
     *  方法一： 判断每个数是否需要加入进行分类
     *  先走 没有元素的, 进行递归
     *  再走有元素的， 进行、递归
     *
     *  最终我们需要的结果是叶子节点
     * @param nums 集合数组
     * @param n 元素的下标
     */

    void dfs(int[]nums , int n) {
        // 递归出口
        // 叶子节点为全部结果
        if(n == nums.length) {
            ret1.add(new ArrayList<>(path1));
            return;
        }

        // 先添加每个位置没有的
        // 相信这个方法一定能把我完成 没有元素的情况
        dfs(nums,n+1);

        // 开始添加
        path1.add(nums[n]);
        // 相信这个方法一定能帮我完成 有元素的情况
        dfs(nums,n+1);

        // 回溯
        path1.remove(path1.size()-1);



    }


    /**
     *  方法二L 分类讨论
     *  有 0 个元素
     *  有 1 个元素
     *  从 0~n 开始不断添加
     *
     *  最终数上的每一个节点都是我们需要的结果
     *
     * @param nums  集合数组
     * @param n 需要到达的第几层
     */

    void dfs2(int[] nums , int n) {
        // 递归出口
        if(n==nums.length) {
            ret.add(new ArrayList<>(path));
            return;
        }

        // 每个节点就是需要的值
        ret.add(new ArrayList<>(path));

        // 遍历开始存放数据
        for(int i = n ; i < nums.length;i++){
            // 添加数据
            path.add(nums[i]);
            // 每一个 i 深搜
            dfs2(nums,i+1);

            // 回溯释放数据
            path.remove(path.size()-1);
        }

    }



    int sum2 ;
    List<Integer> path2;
    public int subsetXORSum(int[] nums) {
        // 计算总和
        sum2=0;
        // 记录路径
        path2 = new ArrayList<>();

        // 开始深搜
        dfs3(nums,0);
        return sum2;
    }

    /**
     * 题目： 找出所有子集之和的总和
     * 总和思路
     * 利用找子集的思路
     * 先使用子集方法一 找出 子集
     * 把每个元素以后异或之和
     * 最终相加即可。
     * @param nums
     * @param pos
     */

    void  dfs3(int[] nums, int pos) {

        // 只有是叶子节点才符合条件
        if(pos == nums.length) {
            int flg =0;
            // 计算总和
            for(int i=0; i < path2.size(); i++) {

                flg ^= path2.get(i);
            }
            sum2 += flg;
            return;
        }

        // 添加没有的
        dfs3(nums, pos+1);

        // 添加有的
        path2.add(nums[pos]);
        dfs3(nums,pos+1);

        // 开始回溯
        path2.remove(path.size()-1);



    }

    public static void main(String[] args) {
        Set<List<Integer>> ret = new HashSet<>();
        List<List<Integer>> lists = new ArrayList<>(ret);
    }

}



class Solution1 {


    static Set<List<Integer>> ret;
   static boolean[] check;
  static   List<Integer> path;
    public static List<List<Integer>> permuteUnique(int[] nums) {
        // 记录路径
        path = new ArrayList<>();
        // 记录布尔值
        check = new boolean[nums.length];

        // 用一个集合去重
        ret = new HashSet<>();

        // 记录返回值
        List<List<Integer>> lists = new ArrayList<>(ret);


        return lists;
    }

    static void  dfs(int[] nums) {
        // 收集叶子节点
        if(path.size()== nums.length) {
            ret.add(new ArrayList(path));
            return;
        }

        // 开始遍历加入元素
        for(int i = 0; i < nums.length; i++) {
            if(!check[i]) {
                // 存放元素
                path.add(nums[i]);
                // 存放完之后加上标识
                check[i]= true;
                // 继续向下走
                dfs(nums);
                // 开始剪枝
                check[i] = false;
                // 开始回溯
                path.remove(path.size()-1);
            }

        }
    }
}




class Solution3 {


    public static void main(String[] args) {
        int[] array = new int[]{1,1,2};
        System.out.println(permuteUnique(array));
    }
    static List<List<Integer>> ret;
    static boolean[] check;
    static List<Integer> path;

    /**
     * 方法一：
     * 利用 条件筛选掉重复的集合
     * 第一个：
     * 筛选掉 上一层用过的元素
     * 第二个：
     * 筛选掉 同一层相同的元素
     *
     * @param nums
     * @return
     */

    public static List<List<Integer>> permuteUnique(int[] nums) {
        // 先进行排序
        Arrays.sort(nums);

        // 记录路径
        path = new ArrayList<>();
        // 记录布尔值
        check = new boolean[nums.length];


        // 记录返回值
        ret = new ArrayList<>();
        dfs(nums);

        return ret;
    }

    static void  dfs(int[] nums) {
        // 收集叶子节点
        if(path.size() == nums.length) {
            ret.add(new ArrayList(path));
            return;
        }




        // 开始遍历加入元素
        for(int i = 0; i < nums.length; i++) {
            // 符合条件的进入
            /**
             *
             * 这个条件是筛选符合条件的
             *
             * check[i] 代表筛选上下层重复的
             *
             * i=0 得到一定成立的第一个元素
             *
             * 并且 左右元素不相等
             *
             * 最后  上层用过的元素也进行往下深入
             */

//            if(!check[i] &&  (i==0 || nums[i-1] != nums[i] || check[i-1] )) {
//                // 存放元素
//                path.add(nums[i]);
//
//                // 存放完之后加上标识
//                check[i]= true;
//
//
//
//                    // 向下一层深搜
//                    dfs(nums);
//
//                    // 开始剪枝
//                    check[i] = false;
//
//                    // 开始回溯, 恢复现场
//                    path.remove(path.size()-1);
//
//                }


            /**
             * 反面思路
             * 筛选掉不符合条件的元素
             *
             * 当 check 标记为 false 的时候就为 同一层
             *
             * check 为 true 就意味着 不同层
             *
             *  所以我们需要 同时满足 后面三个条件 即可
             *
             */
            if (!(check[i] ||  ((i != 0 ) && nums[i-1]==nums[i] && !check[i-1]) ) ){


                    // 存放元素
                    path.add(nums[i]);

                    // 存放完之后加上标识
                    check[i]= true;



                    // 向下一层深搜
                    dfs(nums);

                    // 开始剪枝
                    check[i] = false;

                    // 开始回溯, 恢复现场
                    path.remove(path.size()-1);


            }


            }

        }
}





class Solution4 {

    /**
     *
     * 题目： 全排列 2
     * 方法二 ：
     *
     * 利用 Set 来去重
     *
     * 只要满足的就添加
     * 不满足我们添加无效的方式
     * 就可以达到我们对于本身集合数据的去重
     *
     */
    Set<List<Integer>> ret;
    boolean[] check;
    List<Integer> path;
    public List<List<Integer>> permuteUnique(int[] nums) {
        // 记录路径
        path = new ArrayList<>();
        // 记录布尔值
        check = new boolean[nums.length];

        // 用一个集合去重
        ret = new HashSet<>();

        dfs(nums);
        // 记录返回值
        List<List<Integer>> lists = new ArrayList<>(ret);


        return lists;
    }

    void  dfs(int[] nums) {
        // 收集叶子节点
        if(path.size()== nums.length) {
            ret.add(new ArrayList(path));
            return;
        }

        // 开始遍历加入元素
        for(int i = 0; i < nums.length; i++) {
            if(!check[i]) {
                // 存放元素
                path.add(nums[i]);
                // 存放完之后加上标识
                check[i]= true;
                // 继续向下走
                dfs(nums);
                // 开始剪枝
                check[i] = false;
                // 开始回溯
                path.remove(path.size()-1);
            }

        }


    }


    public static void main(String[] args) {
        String s= "abc";
         char[] ss= s.toCharArray();
        System.out.println(ss[0]);


        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(1);
        stringBuilder.append(2);
        stringBuilder.append(3);
        System.out.println(stringBuilder.deleteCharAt(1));


        s= s.substring(0,s.length()-1);
        System.out.println(s);


    }
}





class Solution5 {
    List<String> ret ;

    String path;

    /**
     * 题目： 电话号码字母组合
     * 利用 数字字符转化为所有字符的可能
     *
     * 方法：
     * 每添加一层
     * 就进行深搜
     * 然后到下一层就换数字字母
     *
     * @param digits 能转化成字母的数字字符
     * @return 返回所以字母组合的全排列
     */
    public List<String> letterCombinations(String digits) {


        // 用作返回值
        ret =  new ArrayList<>();


        // 转换为字符数组
        char[] str = digits.toCharArray();

        if(str.length==0) return ret;

        // 记录路径
        path = new String();


        // 进行深搜
        dfs(str,0);
        return ret;
    }




    public void dfs(char[] str , int pos) {
        // 递归出口
        if(path.length() == str.length)  {
            // 到叶子节点才添加
            ret.add(path);
            return;
        }

        // 得到对应字符
        char[] use = getString(str[pos]);
        for(int i = 0; i < use.length; i++) {

            // 添加每层
            // 添加字符
            path += use[i];

            // 向下换字符串继续添加
            // 开始深搜
            dfs(str,pos+1);

            // 开始回溯
            // 进行恢复现场操作
            path = path.substring(0,path.length()-1);
        }
    }



    // 准备工作
    // 得到目标字符数组
    public char[] getString(char num) {
        String  ret  = "";
        switch (num) {
            case '2' :
                ret += "abc";
                break;
            case '3' :
                ret += "def";
                break;
            case '4' :
                ret += "ghi";
                break;
            case '5' :
                ret += "jkl";
                break;
            case '6' :
                ret += "mno";
                break;
            case '7' :
                ret += "pqrs";
                break;
            case '8' :
                ret += "tuv";
                break;
            case '9' :
                ret += "wxyz";
                break;
        }

        return ret.toCharArray();
    }

}


class Solution6 {

    List<String> ret ;

    StringBuffer path ;
    int left;
    int right;

    int num;


    /**
     * 题目： 括号生成
     * @param n 需要放入的括号的对数
     * @return 返回各种括号组合的全集
     *
     * 方法： 掌握括号的定义
     *
     * 1. 左边括号必须 小于等于括号对数值
     * 2. 左括号 >= 右括号
     *
     */
    public List<String> generateParenthesis(int n) {
        ret = new  ArrayList<>();

        path = new StringBuffer();

        // 分别记录左括号的数据和右括号的数量
        left=0;
        right=0;

        num = n;
        dfs(0);
        // 进行返回
        return ret;

    }



    public void dfs(int pos) {

        // 实现递归出口
        if( pos ==2* num) {
            // 最终的结果是叶子节点
            ret.add(path.toString());
            return;
        }

        /**
         * 只有左括号的数量小于 总对数
         * 才能添加 左括号
         *
         */

        // 添加左括号
        if(left < num ) {
            path.append("(");
            left++;

            // 向下深搜
            dfs(pos+1);
            // 回溯
            // 恢复现场
            left--;
            path.deleteCharAt(path.length()-1);
        }

        /**
         *
         * 添加右括号
         * 左括号 必须保证大于右括号
         * 才可以添加 右括号
         */

        if (right < num  &&  left >  right ) {
            path.append(")");
            right++;
            dfs(pos+1);

            // 回溯
            // 恢复现场
            right--;
            path.deleteCharAt(path.length()-1);
        }



    }




}


class Solution7 {
    List<List<Integer>> ret;
    List<Integer> path;
    int len ;

    /**
     * 题目：  组合
     * 1. 画出决策树
     * 2. 找出依次是从前往后为起点进行排列的规律
     * 3. 注意回溯时，要恢复现场
     * @param n  1~n 范围
     * @param k 每个组合中的元素个数
     * @return 返回所有含有 k 个元素 组合的可能
     */
    public List<List<Integer>> combine(int n, int k) {
        // 路径记录
        path = new ArrayList<>();

        // 用作结果
        ret = new ArrayList<>();

        len = k;

        dfs(1,n);



        return ret;


    }

    public void dfs(int pos,int n) {
        // 存在于叶子节点就插入
        if(path.size() == len) {
            ret.add(new ArrayList<>(path));
            return;
        }

        for(int i = pos; i <= n; i++) {
            // 开始放入
            path.add(i);

            // 深搜
            dfs(i+1, n);

            // 进行回溯
            // 恢复现场
            path.remove(path.size ()-1);

        }

    }

    public static void main(String[] args) {
        Solution7 s = new Solution7();
        System.out.println(s.combine(4, 2));
    }
}


class Solution8 {
    int sum;
    int ret ;


    /**
     *  题目： 目标和
     * 方法：
     * 1. 先进行相加
     * 2. 然后深搜回溯
     * 3. 再进行相减
     * 4. 最后进行深搜回溯
     *
     * @param nums 所有正整数元素的数组
     * @param target  目标值
     * @return 返回所有可能的个数
     *
     */
    public int findTargetSumWays(int[] nums, int target) {
        // 用于统计总和
        sum =0;

        // 作为最终结果
        ret = 0;

        // 进行深搜
        dfs(nums,0,target);


        return ret;
    }

    public void dfs(int[]nums, int pos, int target) {
        // 到达叶子节点时才判断
        if(pos == nums.length) {
            if(sum == target) {
                ret++;
            }
            return;
        }


        // 加入元素
        sum += nums[pos];
        dfs(nums,pos+1, target);

        // 进行回溯
        // 恢复现场
        sum -= nums[pos];

        // 减去元素
        sum -=nums[pos];
        dfs(nums, pos+1, target);

        // 进行回溯
        // 恢复现场
        sum += nums[pos];

    }




}


